package com.camus.datastructureandalgorithm.algorithm.sort;

/**
 * @author jie.deng
 * 插入排序
 */
public class InsertSortArray implements SortArray {

    @Override
    public int[] sortArray(int[] nums) {
        if (nums == null || nums.length == 0) {
            return nums;
        }
        // 分为已排序区间和未排序区间
        // 每次从未排序区间取第一个元素，将其放到已排序区间的合适的位置
        // 第i轮，已排序区间有i个元素。将nums[i]插入到nums[0...i-1]的合适位置
        int length = nums.length;
        for (int i = 1; i < length; i++) {
            int num = nums[i];
            int j = i - 1;
            for (; j >= 0; j--) {
                if (nums[j] <= num) {
                    break;
                }
                nums[j + 1] = nums[j];
            }
            nums[j + 1] = num;
        }

        return nums;
    }

}
